package 动态规划.回文串;

public class 让字符串成为回文串的最少插入次数_1312 {
    public int minInsertions(String s) {
        int n = s.length();
        /*
        dp:对于s[i..j]，最少需要插入dp[i][j]次才能变成回文串
        dp默认被0填充，这里面包含了base case：i==j，单个字符本身就是回文串，所需操作为0次
        */
        int[][] dp = new int[n][n];

        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    //dp[i+1][j-1]：看成字符串首部尾部各一个指针，都往中间移动
                    dp[i][j] = dp[i + 1][j - 1];//无需操作
                } else {
                    /*dp[i+1][j]：把s[i+1,..,j]变成回文串的代价
                        最后还要+1的原因：
                            假如令s[i,...,j-1]成了回文串，那么只需要在s[i,...,j-1]
                            的左边插入一个s[j]，就一定可以把s[i..j]变成回文串
                    */
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
                }
            }

        }

        return dp[0][n - 1];
    }
}
